class Solution
{
public:
    int reinitializePermutation(int n)
    {
        int i = n / 2;
        int step = 1;
        while (i != 1)
        {
            if (i & 1)
            {
                i = n / 2 + (i - 1) / 2;
            }
            else
            {
                i = i / 2;
            }
            ++step;
        }
        return step;
    }
};